package sort;

import java.util.concurrent.ThreadLocalRandom;

public class SevenSortReview1 {
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();

    public void insertSort (int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i; j >= 0 && arr[j + 1] < arr[j]; j--) {
                swap(arr,j,j + 1);
            }
        }
    }

    public void insertSortOP (int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i + 1] < arr[i]) {
                int tmp = arr[i + 1];
                int index = i;
                for (; index >= 0 && arr[index] > tmp; index--) ;
                for (int k = i; k > index; k--) {
                    arr[k + 1] = arr[k];
                }
                arr[index + 1] = tmp;
            }
        }
    }

    public void selectSort1 (int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            swap(arr,min,i);
        }
    }

    public void selectSort2 (int[] arr) {
        int start = 0,end = arr.length - 1;
        while (start < end) {
            int min = start,max = start;
            for (int i = start; i <= end; i++) {
                if (arr[i] > arr[max]) {
                    max = i;
                }
                if (arr[i] < arr[min]) {
                    min = i;
                }
            }
            swap(arr,start,min);
            if (max == start) {
                max = min;
            }
            swap(arr,end,max);
            start++;
            end--;
        }
    }

    public void bubbleSort (int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j + 1);
                }
            }
        }
    }

    public void shellSort (int[] arr) {
        int gap = arr.length / 2;
        while (gap > 0) {
            for (int i = 0; i < arr.length - gap; i++) {
                for (int j = i; j >= 0 && arr[j + gap] < arr[j]; j -= gap) {
                    swap(arr, j, j + gap);
                }
            }
            gap /= 2;
        }
    }

    public void heapSort (int[] arr) {
        for (int i = (arr.length - 2) / 2; i >= 0 ; i--) {
            siftDown(arr,i,arr.length - 1);
        }
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr,0,i);
            siftDown(arr,0,i - 1);
        }
    }

    private void siftDown(int[] arr, int i, int length) {
        int child = 2 * i + 1;
        if (child > length) {
            return;
        }
        if (child + 1 <= length && arr[child + 1] > arr[child]) {
            child++;
        }
        if (arr[i] < arr[child]) {
            swap(arr, i, child);
        }
        i = child;
        siftDown(arr, i, length);
    }

    public void quickSort (int[] arr) {
        quickSortInternal(arr,0, arr.length - 1);
    }

    private void quickSortInternal (int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = partition1(arr, left ,right);
        quickSortInternal(arr, left, mid - 1);
        quickSortInternal(arr, mid + 1, right);
    }

    private int partition1(int[] arr, int left, int right) {
        int randomIndex = random.nextInt(left,right);
        swap(arr, left, randomIndex);
        int v = arr[left];
        int i = left,j =  left + 1;
        while (j <= right) {
            if (arr[j] < v) {
                swap(arr,i + 1, j);
                i++;
            }
            j++;
        }
        swap(arr, i, left);
        return i;
    }

    private int partition2 (int[] arr, int left, int right) {
        int randomIndex = random.nextInt(left,right);
        swap(arr, left, randomIndex);
        int v = arr[left];
        int i = left + 1,j = right;
        while (true) {
            while (i <= j && arr[i] < v) {
                i++;
            }
            while (i <= j && arr[j] > v) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
            j--;
            i++;
        }
        swap(arr, left, j);
        return j;
    }

    public void mergeSort (int[] arr) {
        int[] tmp = new int[arr.length];
        mergeSortHelper(arr, 0, arr.length - 1, tmp);
    }

    private void mergeSortHelper(int[] arr, int left, int right, int[] tmp) {
        if (left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeSortHelper(arr, left, mid, tmp);
        mergeSortHelper(arr, mid + 1, right, tmp);
        if (arr[mid] > arr[mid + 1]) {
            merge(arr, left, mid, right, tmp);
        }
    }

    private void merge(int[] arr, int left, int mid, int right, int[] tmp) {
        int i = left, j = mid + 1;
        int index = left;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                arr[index++] = arr[i++];
            }else {
                arr[index++] = arr[j++];
            }
        }
        while (i <= mid) {
            arr[index ++] = arr[i++];
        }
        while (j <= right) {
            arr[index++] = arr[j++];
        }
        for (int k = left; k <= right; k++) {
            arr[k] = tmp[k];
        }
    }

    private void swap(int[] arr, int j, int i) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }
}